package com.fr.lintcode;

/**
*作者：furong
*日期：2017年2月6日
*时间：上午10:28:55
*/
public class Q119 {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() == 0) {
            if (word2 == null) {
                return 0;
            } else {
                return word2.length();
            }
        }
        if (word2 == null || word2.length() == 0) {
            return word1.length();
        }
        int l1 = word1.length();
        int l2 = word2.length();
        int dp[][] = new int[l1 + 1][l2 + 1];
        for (int i = 0; i <= l1; i++) {
            for (int j = 0; j <= l2; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = Math.min((word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1) + dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);
                }
            }
        }
        return dp[l1][l2];
    }
}
